package 中等.二分查找;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：
 * p[0] = start
 * p[i] 和 p[i+1] 的二进制表示形式只有一位不同
 * p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/circular-permutation-in-binary-representation
 */
public class 循环码排列_1238 {

    public static void main(String[] args) {

        circularPermutation(3, 0);

    }

    /**
     * 公式法求格雷码
     * 1，格雷码可以通过 [0,2^n-1] 数字求出对应的格雷码
     * 每个数字的格雷码求法
     * 0 1 0 1
     * 与自身 >>1 的数字进行 ^ 运算
     * 0 0 1 0
     * 即 x^(x>>1)
     * 2，然后找到 start 对应的格雷码，往后循环取 2^n 个数
     */
    public static List<Integer> circularPermutation(int n, int start) {
        List<Integer> list = new ArrayList<>();
        int[] record = new int[(int) Math.pow(2, n)];
        for (int i = 0; i < record.length; i++) {
            record[i] = i ^ (i >> 1);
        }
        int bIdx = 0;
        while (record[bIdx] != start) bIdx++;

        for (int i = 0; i < record.length; i++) {
            int real = (i + bIdx) % record.length;
            list.add(record[real]);
        }

        return list;
    }

}
